package algorithm_demo.demo04;

import java.util.PriorityQueue;

/**
 * 堆和排序是贪心最常用的手段
 * <p>
 * 贪心算法
 *
 * @author Api
 * @date 2023/2/15 23:42
 */
public class Code05_LessMoney {
    /*
     * 一根金条切成两半，是需要花费和长度数值一样的铜板
     * 比如长度为20的金条，不管怎么切，都需要花费20个铜板。一群人想整分整块金条，怎么分最省铜板？
     * 例如，给定数组{10,20,30},代表一共三个人，整块金条长度为60，金条要分成10,20,30三个部分。
     * 如果先把长度60的金条分成10,50，花费60；再把长度50的金条分成20,30，花费50；一共花费110铜板。
     * 但如果先把长度60的金条分成30和30，花费60，再把长度30金条分成10和20，花费30；一共花费90铜板。
     * 输入一个数组，返回分割的最小代价。
     *
     * */

    public static void main(String[] args) {
        int[] arr = new int[]{2, 4, 1, 5, 3, 2};
        int i = lessMoney2(arr);
        System.out.println(i);
    }
    /*哈夫曼树*/

    public static int lessMoney2(int[] arr) {
        //小根堆
        PriorityQueue<Integer> pQ = new PriorityQueue<>();
        for (int j : arr) {
            pQ.add(j);
        }
        int sum = 0;
        int cur = 0;
        while (pQ.size() > 1) {
            cur = pQ.poll() + pQ.poll();
            sum += cur;
            pQ.add(cur);
        }
        return sum;
    }
}
